package com.LeeCode;

/**
 * 第 k 个缺失的正整数
 */

public class Code1539 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int k = 2;
        System.out.println(new Code1539().findKthPositive(nums, k));
    }

    public int findKthPositive(int[] arr, int k) {
        int left = 0, right = 2000;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            // 缺失整数的个数
            int count = mid - lowerBound(arr, mid + 1);
            if (count >= k)
                right = mid;
            else
                left = mid;
        }
        return right;
    }

    // 查找第一个>=target的下标
    private int lowerBound(int[] nums, int target) {
        int left = -1, right = nums.length;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target)
                right = mid;
            else
                left = mid;
        }
        return right;
    }
}
